import java.util.ArrayList;
import java.util.List;

public class Solution93 {
    List<String> res;

    public List<String> restoreIpAddresses(String s) {
        res = new ArrayList<>();
        dfs(s, new int[4], 0, 0);
        return res;
    }

    void dfs(String s, int[] ip, int index, int k) {
        if (k == 4) {
            if (index == s.length()) {
                StringBuilder stringBuilder = new StringBuilder();
                for (int i : ip) {
                    stringBuilder.append(i).append('.');
                }
                res.add(stringBuilder.deleteCharAt(stringBuilder.length() - 1).toString());
            }
            return;
        }
        if (index < s.length()) {
            int a = s.charAt(index) - '0';
            index++;
            ip[k] = a;
            dfs(s, ip, index, k + 1);
            if (ip[k] == 0) {
                return;
            }
        }
        if (index < s.length()) {
            int b = s.charAt(index) - '0';
            index++;
            ip[k] = ip[k] * 10 + b;
            dfs(s, ip, index, k + 1);
            if (ip[k] > 25) {
                return;
            }
        }
        if (index < s.length()) {
            int c = s.charAt(index) - '0';
            index++;
            ip[k] = ip[k] * 10 + c;
            if (ip[k] > 0 && ip[k] <= 255) {
                dfs(s, ip, index, k + 1);
            }
        }
    }
}
